package leetcode;

import java.util.Arrays;

/**
 * 最接近三数之和
 */
public class ThreeSumClosest {
    public static void main(String[] args) {
        int[] nums = {-4, -2, 1, -5, -4, -4, 4, -2, 0, 4, 0, -2, 3, 1, -5, 0};
        int res = threeSumClosest(nums, 15);
        System.out.println(res);
    }

    public static Integer threeSumClosest(int[] nums, int target) {
        // 排序
        Arrays.sort(nums);

        int best = Integer.MAX_VALUE;
        // 第二步再遍历
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            // 保证和上一次枚举的元素不相等,加上不会出错，但是这个num[i]已经计算过了，没必要重复计算
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            // 使用双指针枚举 b 和 c
            int j = i + 1, k = length - 1;

            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                // 如果和为 target 直接返回答案
                if (sum == target) {
                    return target;
                }

                // 根据差值的绝对值来更新答案
                if (Math.abs(sum - target) < Math.abs(best - target)) {
                    best = sum;
                }

                if (sum > target) {
                    k--;
                } else {
                    j++;
                }
            }
        }
        return best;
    }
}
